强化学习 · 第四章 · 专题动画
从一组方程
到一套算法
上一章把长期问题压缩成贝尔曼方程;这一章回答最后一跳:这组方程到底怎么解。同样是解方程,手里的信息不同,走的路也不同。
① 策略迭代
② 值迭代
③ DP 与 LP
④ 采样强化学习
⑤ GPI
一句话方程不变;变的只是期望怎么算、最优怎么找、状态装不装得下。
这一章的解方程控制台
V = R + γPV · V* = maxa Q*
先看手里有什么信息
DP模型已知、状态可枚举:全枚举期望,反复做备份
LP模型已知:把 max 展开成约束,换一个优化视角
采样模型未知:用真实走一步,代替期望求和
04.1 · 策略迭代
评估一步,改进一步,直到不再变化
① 策略迭代›
② 值迭代›
③ DP·LP›
④ 采样›
⑤ GPI
1策略评估:固定 π,把价值算清
直接解线性方程,或反复套用期望方程,逼近到满意精度。
2策略改进:对 Q 取贪心
每个状态都改选 Qπ(s,a) 最大的动作。
3Q 的骨架仍是“奖励 + 折扣未来”
Qπ(s,a) = R + γΣP·Vπ(s′):仍是上一章那条备份公式。
4终止:π′ = π
新策略对自身已贪心,就满足贝尔曼最优方程。
闭环评估负责“算清现在”,改进负责“往上走一步”;两者交替,直到没有更好的动作可选。
04.1b · 两状态小世界演示
亲手跑一遍:评估、改进,再评估
① 策略迭代›
② 值迭代›
③ DP·LP›
④ 采样›
⑤ GPI
屏幕上这些数字分别代表什么
V(s)这个状态以后一直按当前策略走下去,折扣奖励加起来的总和 —— 本轮 0 / 1.0,再评估 9 / 10
Q(s,a)即时奖励 + γ × 下一步状态的 V —— 本例依次算出 0.9、1.9、8.1、9.1
r 与 γr:走一步当场拿到的奖励(+1 或 0);γ = 0.9:下一步只算九折
当前策略π₀ = (家: 躺平,公司: 回家) · 随机初始化
贪心改进π₁ = (家: 上班,公司: 工作)
停机π₂ = π₁ · 策略不再变化
策略评估 · 固定 π₀,反复代入到不再变化
V(家) = 0 + 0.9·V(家) → 0 V(公司) = 1 + 0.9·V(家) → 1.0
读数:0 / 1 是走一步当场拿到的奖励,0.9 是 γ;解出的 0 / 1.0 = 按 π₀ 走时家 / 公司各值多少
策略改进 · 用刚解出的 Vπ₀ 比一步价码 Q
Q(家,上班) = 0 + 0.9 × 1.0 = 0.9 > 0(躺平)
Q(公司,工作) = 1 + 0.9 × 1.0 = 1.9 > 1.0(回家)
读数:0 / 1 是即时奖励,1.0 是公司的 V;0.9 / 1.9 = 先做这个动作一次,连同之后的价值
策略评估 · 固定 π₁,公司陷入工作自循环
V(公司) = 1 + 0.9·V(公司) → 10 V(家) = 0.9 × 10 → 9
读数:10 = 每轮 1 + 0.9×上一轮的极限(下方迭代轨迹的 ∞ 列);9 = 家的即时奖励 0 + 0.9 × 10
策略改进 · 用 Vπ₁ 再比一次 Q:两处都不换
家:上班 0 + 0.9 × 10 = 9 > 躺平 0 + 0.9 × 9 = 8.1
公司:工作 1 + 0.9 × 10 = 10 > 回家 1 + 0.9 × 9 = 9.1
读数:8.1 / 9.1 = 改选另一个动作后、再乘一步折扣的价码,都比现在的选择低
停机 · 改进不再改动任何一个状态
π₂ = π₁ = (上班, 工作) → π*,V* = (9, 10)
读数:9 / 10 就是最优价值 V*(家) / V*(公司),与上一轮评估完全一致
| 轮 | 策略 π | 评估出的 V | 贪心之后 |
| 0 |
π₀ = (躺平, 回家) |
Vπ₀ = (0, 1.0) |
π₁ = (上班, 工作)变了 |
| 1 |
π₁ = (上班, 工作) |
Vπ₁ = (9, 10) |
π₂ = π₁不变 |
| 停 |
π′ = π → 输出 π* = (上班, 工作),V* = (9, 10) |
括号内依次是 V(家)、V(公司);「贪心之后」这一列,就是下一行要用的新策略。
评估 π₀ 的迭代轨迹 · 每轮把等号右边的 V 换成上一轮的数值
| k | 0 | 1 | 2 | 3 | 4 | ⋯ | ∞ |
| V(家) | 0 | 0 | 0 | 已收敛,不再变化 | 0 |
| V(公司) | 0 | 1.00 | 1.00 | 已收敛,不再变化 | 1.0 |
评估 π₁ 的迭代轨迹 · 每轮 1 + 0.9×上一轮,一步步爬向 10
| k | 0 | 1 | 2 | 3 | 4 | ⋯ | ∞ |
| V(家) | 0 | 0 | 0.90 | 1.71 | 2.44 | ⋯ | 9 |
| V(公司) | 0 | 1.00 | 1.90 | 2.71 | 3.44 | ⋯ | 10 |
为什么必停每一轮都严格变好,而两状态两动作一共只有 4 种策略——有限轮之后,必然 π′ = π。
04.2 · 策略改进定理
为什么贪心一步,不会把策略改坏
① 策略迭代›
② 值迭代›
③ DP·LP›
④ 采样›
⑤ GPI
Qπ(s,π′(s)) = maxa Qπ(s,a) ≥ Vπ(s)
数字哪里来 · 上一章三动作算例(状态 s,π = 0.5 / 0.3 / 0.2)
a₁π=0.5Q=+1.20
a₂π=0.3Q=+0.50
a₃π=0.2Q=−0.30
= 0.5×1.20 + 0.3×0.50 + 0.2×(−0.30)
= max{1.20, 0.50, −0.30} = Q(s,a₁)
+0.51这一步立刻拿到的优势;未来再按新策略展开,价值只会继续抬升。
第一步:看一步 Q
把新策略代入旧价值,先得到一个不低于 Vπ 的起点:Qπ(s,π′(s)) ≥ Vπ(s)。
解法:maxa Qπ(s,a) = Q(s,a₁) = 1.20 ≥ Vπ(s) = 0.69
第二步:反复代入
每一步都不降,未来每一次备份也都不降,因此整条价值轨迹满足 Vπ′ ≥ Vπ。
解法:把 Vπ′ ≥ 1.20 代回 Vπ′=Rπ′+γPπ′Vπ′,下界只升不降 ⇒ Vπ′ ≥ 1.20 ≥ 0.69
单调性策略可以不变,但绝不会越改越差;有限个策略 + 严格改进 = 策略迭代必然终止。
04.3 · 何时停,贵在哪
终止条件很干脆,代价却藏在内层
① 策略迭代›
② 值迭代›
③ DP·LP›
④ 采样›
⑤ GPI
停机:策略不再变化
π′ = π
再改也没有更好的动作可选,当前策略满足贝尔曼最优方程。
成本画像:贵在“评估做满”
解方程O(n³)
一次备份O(n²)
状态规模n 大 → 痛
轮数少,不代表总成本低:每一轮都要先把评估做透。
问能不能少评估一点?
不等旧策略完全收敛,提前进入改进。
→
答只做一次备份:值迭代
评估与改进合并成一步,用更便宜的轮次换更多轮数。
取舍策略迭代是“想清楚再走”,值迭代是“边走边想”。下一幕把这条更便宜的路线拆开。
04.4 · 值迭代
不等评估做满,每轮只做一次最优备份
① 策略迭代›
② 值迭代›
③ DP·LP›
④ 采样›
⑤ GPI
值迭代Vk+1(s) = maxa [ R(s,a) + γ Σs′P(s′|s,a) Vk(s′) ]
右端就是贝尔曼最优算子 T*:从任意 V0 出发,反复应用它。
| k | s₁ | s₂ | s₃ | s₄ | s₅ |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1.000 | 0 |
| 2 | 0 | 0 | 0.900 | 1.000 | 0 |
| 3 | 0 | 0.810 | 0.900 | 1.000 | 0 |
| 4 | 0.729 | 0.810 | 0.900 | 1.000 | 0 |
收敛后对 V* 做一次贪心,就能导出 π*。
第 1 轮备份 · 每个状态做一次「奖励 + γ × 后继价值」
V₁(s₄) = 1 + 0.9 × V₀(s₅) = 1 + 0.9×0 = 1.000 V₁(s₁..s₃) = 0 + 0.9 × 0 = 0
读数:1 是迈进出口的奖励,0.9 是 γ;V₀ 全是 0,所以第一轮只有 s₄ 亮起来(走廊里每格只有「前进」一条路,max 不用比)
第 2 轮备份 · 奖励往左传一格,旧格子照旧更新
V₂(s₃) = 0 + 0.9 × V₁(s₄) = 0.9 × 1.000 = 0.900 V₂(s₄) = 1 + 0.9 × V₁(s₅) = 1.000
读数:走一步自己的奖励是 0,所以每往左挪一格就乘一次 0.9;s₄ 那一格已经到顶,保持 1
第 3、4 轮备份 · 同一个式子继续往左推,直到 s₁
V₃(s₂) = 0 + 0.9 × V₂(s₃) = 0.9 × 0.900 = 0.810
V₄(s₁) = 0 + 0.9 × V₃(s₂) = 0.9 × 0.810 = 0.729
读数:整条走廊收敛到 (0.729, 0.810, 0.900, 1.000, 0),就是 V*;每轮只做一次这样的备份,就是值迭代
为什么一定收敛上一章已经证明 T* 是 γ-压缩:每扫一遍,离 V* 的距离至多剩原来的 γ 倍。
04.5 · 两种迭代的谱系
不是对立,只是评估做了几次
① 策略迭代›
② 值迭代›
③ DP·LP›
④ 采样›
⑤ GPI
同一个旋钮:每轮评估做几次?
1 次
值迭代k 次
截断策略迭代做满
策略迭代
示例:还是「公司」这一格(工作 +1,γ = 0.9)
评估一次 = V ← 1 + 0.9 × V
四个数是同一式子的第 k 次结果:算得越多,越贴近 V* = 10
每轮成本与轮数
策略迭代轮数少
策略迭代每轮贵
值迭代轮数多
值迭代每轮便宜
把初始误差压到 1/1000 的轮数
γ = 0.966
γ = 0.99688
轮数 k ≈ ln1000 / ln(1/γ):γ 越接近 1 压缩越弱,66 → 688,十倍还多。
还可以更灵活:只扫一部分状态(异步 DP),或优先更新变化大的状态(优先扫描)。
选择状态不多、想少走几轮 → 策略迭代;状态很多、单轮要便宜 → 值迭代。
04.6 · DP 的门槛与线性规划
模型已知之后,还有一道规模门槛
① 策略迭代›
② 值迭代›
③ DP·LP›
④ 采样›
⑤ GPI
线性规划minV ΣsV(s) s.t. V(s) ≥ R(s,a) + γ Σs′P(s′|s,a)V(s′) ∀s,a
把 max 展开成“每个动作都成立”的不等式;最优解处约束最紧。
1模型已知
P 与 R 必须能查询,否则期望和 max 都算不出来。
2状态可枚举
每轮扫描所有状态;状态越大,单轮成本越高。
!维数灾难
状态数随变量个数指数增长;每轮都要扫全表,结构上就扛不住。
把整张 V 表当成一个点:怎么读这张图
①横轴 V(家)、纵轴 V(公司):随便猜一组值,就是图上一个点(如左下的「猜的 3, 4」)。
②每条备份不等式画成一条线:要「不违反」,点就只能待在线的一侧。
③目标是把总和压小:只能往左下推,推到不能再推 = 两线交点。
算一下:公司 ≥ 1 + 0.9×公司 ⟹ 公司 ≥ 10;家 ≥ 0.9×公司 ⟹ 家 ≥ 9;最小和 = 19。
LP 的理论意义大;工程上,值迭代通常更直接。
阴影 = 所有「不违反备份」的 (V(家), V(公司)),只剩右上角一小块;红虚线是目标和 19 的等值线,压到底就停在顶点。另两条备份在这里是松的。
同一件事DP 在状态空间里扫表,LP 在可行域里找顶点;都在解同一组最优方程。
04.7 · 从期望到样本
模型不知道,就用真实走一步代替求和
① 策略迭代›
② 值迭代›
③ DP·LP›
④ 采样›
⑤ GPI
有模型:对全部下一状态求和
Σs′ P(s′|s,a) V(s′)
当前 (s,a)
↘s′₁概率0.7价值V₁
↗s′₂概率0.3价值V₂
= 0.7 × V₁ + 0.3 × V₂
两条支路都要算,按概率加权
无模型:走一步,拿一个样本
样本平均 ≈ E[V(s′)]
真实一步
→实际落到s′ = s′₂
→带回价值V(s′₂) = V₂
= V₂
这次 0.7 那条没抽到,只拿到 0.3 那条的样本;多走几次取平均,才逼近 0.7×V₁ + 0.3×V₂
屏幕上这些数字分别是什么
0.7 / 0.3 转移概率 P:同一个动作,有 70% 的机会落到 s′₁、30% 的机会落到 s′₂(两条加起来 = 1,所以才需要“求和”)。
V₁ / V₂ 真的落到 s′₁ / s′₂ 之后,那个状态本身值多少,也就是备份里的 V(s′)。
估计值 ← 估计值 + α [ 目标 − 估计值 ]
α 是学习率(取 0 到 1):这一步的新信息占多少权重;γ 是折扣,和前面一样 0.9。
方括号里是误差信号;目标怎么取,决定了算法叫什么名字。
蒙特卡洛:目标 = 整条轨迹回报
时序差分:目标 = 一步奖励 + γV(s′)
自举:有偏,但方差更小
分界线不在“用不用神经网络”,而在期望怎么算:求和还是采样。
04.8 · 同策略与异策略
下一个动作怎么选,分出了两个家族
① 策略迭代›
② 值迭代›
③ DP·LP›
④ 采样›
⑤ GPI
SARSA · 同策略
r + γ Q(s′, a′)
a′ 是行为策略真正选出的下一个动作
行为策略 = 目标策略
Q-LEARNING · 异策略
r + γ maxa Q(s′, a)
不管行为策略,直接假设下一步选最优
行为策略 ≠ 目标策略
这两个算法后面会详细讲解;这里先用同一个数字例子,让它们各走一步,看差别落在哪一个数上。
| 算例 | 目标 | 误差项 | 更新后的 Q |
| 已知 | Q = 0.50,r = 0.20,γ = 0.9 | 步长 α = 0.10 | — |
| SARSA | 0.20 + 0.9 × 0.60 = 0.74 | 0.74 − 0.50 = 0.24 | 0.50 + 0.10×0.24 = 0.524 |
| Q-Learning | 0.20 + 0.9 × 0.80 = 0.92 | 0.92 − 0.50 = 0.42 | 0.50 + 0.10×0.42 = 0.542 |
把表格拆成四步算:0.20 是这一步真拿到的奖励,0.9 是折扣 γ(未来打 9 折),0.10 是学习率 α(只信十分之一),0.50 是现在的估计
绿色 = SARSA(下一步用真会选的那个动作 Q = 0.60) | 金色 = Q-Learning(下一步用最好的那个动作 Q = 0.80)
① 目标:这一步实际值多少
0.20 + 0.9 × 0.60 = 0.74
0.20 + 0.9 × 0.80 = 0.92
② 误差:比 0.50 高多少
0.74 − 0.50 = 0.24
0.92 − 0.50 = 0.42
③ 改动:只挪十分之一
0.10 × 0.24 = 0.024
0.10 × 0.42 = 0.042
④ 新估计:旧值加改动
0.50 + 0.024 = 0.524
0.50 + 0.042 = 0.542
为什么不直接把 0.50 改成 0.74?因为 α = 0.10 只让它信这一步 10%。两个算法的差别全在第一步:未来按 0.60 还是 0.80 折,目标就差 0.18,最后的值只差 0.018。
离散动作:SARSA / Q-Learning 是常见起点
连续动作:max 不好取,转向策略梯度
Actor-Critic:策略 + Critic,再降方差
一句话SARSA 把“我实际会怎么走”算进去;Q-Learning 把“理论上最好怎么走”当成目标。
04.9 · 广义策略迭代与选择
评估与改进互相拉扯,最后停在同一点
① 策略迭代›
② 值迭代›
③ DP·LP›
④ 采样›
⑤ GPI
1模型能不能拿到?
能 → DP / LP;不能 → 采样方法。
2动作离散还是连续?
离散 → 可以 max;连续 → 策略梯度。
3数据能不能反复用?
能反复用 → 异策略;只能用新采的 → 同策略。
结果三个问题答完,大部分算法选项已经被排除。
一条轨迹 → 一组方程 → 三条解法 → 一套算法地图
片尾 · 出品说明
朝露记出品
内容梳理
讲解配音
动画编排
第四章 · 完
下一章 · 从一套算法到一页纸
解